import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * Created by IntelliJ IDEA.
 * User: Alexander Fedulin
 * Date: 01.11.11
 * Time: 12:58
 * To change this template use File | Settings | File Templates.
 */
public class Pet {

    private String problem_input = "pet.in";
    private String problem_output = "pet.out";
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter out;
    private long[][] t = new long [15][15];
    private long[][] d = new long[15][15];

    String nextToken() throws IOException
    {
        while (st == null || !st.hasMoreTokens())
               st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }
    long n;
    int k;
    int l[] = new int[15];

    void load() throws IOException
    {
        n = nextLong();
        k = nextInt();
        for (int i = 0; i < k; i++)
            l[i] = nextInt();
        Arrays.sort(l, 0, k);
    }
    long v[] = new long[15];
    long a[][] = new long[15][15];
    final long mod = 1000000007;
    void solve()
    {
        v[0] = 1;
        for (int i = 1; i < 15; i++)
        {
            v[i] = 0;
            for (int j = 0; j < k && i - l[j] >= 0; j++)
            {
                v[i] += v[i - l[j]];
                if (v[i] >= mod) v[i] -= mod;
            }
        }
        for (int i = 0; i < 15; i++)
        {
            Arrays.fill(a[i], 0);
            Arrays.fill(d[i], 0);
        }
        for (int i = 0; i < 15; i++)
            d[i][i] = 1;
        for (int i = 0; i < 14; i++)
        {
            a[i+1][i] = 1;
        }
        for (int i = 0; i < k; i++)
        {
            a[15 - l[i]][14]++;
        }
        while (n > 0)
        {
            if ((n & 1) > 0)
            {
                for (int i = 0; i < 15; i++)
                    for (int j = 0; j < 15; j++)
                    {
                        t[i][j] = 0;
                        for (int k = 0; k < 15; k++)
                        {
                            t[i][j] += (d[i][k] * a[k][j]) % mod;
                            if (t[i][j] >= mod) t[i][j] -= mod;
                        }
                    }
                for (int i = 0; i < 15; i++)
                    for (int j = 0; j < 15; j++)
                         d[i][j] = t[i][j];
            }
            n >>= 1;
            for (int i = 0; i < 15; i++)
                    for (int j = 0; j < 15; j++)
                    {
                        t[i][j] = 0;
                        for (int k = 0; k < 15; k++)
                        {
                            t[i][j] += (a[i][k] * a[k][j]) % mod;
                            if (t[i][j] >= mod) t[i][j] -= mod;
                        }
                    }
                for (int i = 0; i < 15; i++)
                    for (int j = 0; j < 15; j++)
                         a[i][j] = t[i][j];
        }
        int res = 0;
        for (int i = 0; i < 15; i++)
        {
            res += (d[i][0] * v[i]) % mod;
            if (res >= mod) res -= mod;
        }
        out.println(res);
    }
    void run()
    {
        try
        {
            boolean online_judge = System.getProperty("ONLINE_JUDGE") != null;
            if (online_judge)
            {
                br = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(new OutputStreamWriter(System.out));
            }
            else
            {
                br = new BufferedReader(new FileReader(problem_input));
                out = new PrintWriter(new FileWriter(problem_output));
            }
            int T = nextInt();
            for (int i = 0; i < T; i++)
            {
                load();
                solve();
            }
            out.close();
        }
        catch (Exception e)
        {
            e.printStackTrace();
            System.exit(42);
        }
    }
    int nextInt() throws IOException
    {
        return Integer.parseInt(nextToken());
    }
    long nextLong() throws IOException
    {
        return Long.parseLong(nextToken());
    }
    double nextDouble() throws IOException
    {
        return Double.parseDouble(nextToken());
    }

    public static void main(String args[])
    {
        new Pet().run();
    }
}
